// 插入排序
// 考察的元素从 i=1 开始
// seq[i] 元素和前面i个已经排序的元素比较
// e.g.   [5, 4, 1, 2, 9]
// step1: [4, 5, 1, 2, 9]
// step2: [1, 4, 5, 2, 9]
// step3: [1, 2, 4, 5, 9]
// step4: 不用交换元素 break

package sort

func InsertSort(arr []int)  {
	//count := 0
	n := len(arr)
	for i := 1; i < n; i++ {
		// 寻找元素seq[i]合适的插入位置
		for j := i; j > 0 && arr[j] < arr[j-1] ; j-- {
			arr[j-1], arr[j] = arr[j], arr[j-1]
			//count++
		}
	}
	//fmt.Printf("switch %d\n", count)
}

func InsertSortAdvance(arr []int)  {
	n := len(arr)
	for i := 1; i < n; i++ {
		// 寻找元素seq[i]合适的插入位置
		e := arr[i]
		var j int
		for j = i; j > 0 && arr[j-1] > e; j-- {
			arr[j] = arr[j-1]
		}
		arr[j] = e
	}
}
